// 常规做法
// function countingBits(n) {
//   let result = []
//   for (let i = 0; i <= n; i++) {
//     result[i] = count(i)
//   }
//   return result
// }

// function count(i) {
//   // if (i === 0) return 0
//   let c = 0
//   while (i > 0) {
//     i = i & (i - 1)
//     c += 1
//   }
//   return c
// }

// 递推公式 3 种 递推公式
function countingBits(n) {
  let result = Array(n + 1).fill(0)
  for (let i = 1; i <= n; i++) {
    result[i] = result[i & (i - 1)] + 1
  }
  return result
}

let r = countingBits(5)

console.log(r)
